package com.algorithm.排序.基于计数的排序;

import com.algorithm.排序.Sort;

//优化后的计数排序，解决若干问题
@SuppressWarnings("all")
public class 计数排序_优化 extends Sort<Integer> {
    @Override
    protected void sort() {
        //找出array[]数组中最大和最小的两个数
        int max = array[0];
        int min = array[0];
        for (int i = 0; i < array.length; i++) {
            if (array[i] > max){
                max = array[i];
            }
            if (array[i] < min) {
                min = array[i];
            }
        }

        //开辟内存空间，存储每个整数出现的次数（累加式的次数）
        //只开辟 max - min + 1 大小的内存空间，目的是为了节省空间
        int[] counts = new int[max - min + 1];

        // 1. 先统计每个整数出现的次数，并且存储在 counts[] 里面
        for (int i = 0; i < array.length; i++) {
            //array[i] 的元素数量放在counts[]数组的位置索引应该是 array[i]-min
            counts[array[i] - min] ++;
        }
        // 2. 再将每个整数中出现的次数，累加前面元素出现次数，存储在 counts[] 中
        for (int i = 1; i < counts.length; i++) {
            counts[i] += counts[i - 1];
        }

        //从后往前遍历数组，将它放在有序数组中的合适的位置
        int[] newArray = new int[array.length];
        for (int i = array.length - 1; i >= 0; i--) {
            // array[i] 的元素数量放在 counts[]数组的位置索引为 counts[array[i] - min],
            //并且 `--counts[array[i] - min` 的值恰好就是 array[i] 在新的排序数组 newArray中的索引位置
            // newArray[--counts[array[i] - min]] 意为先将counts[array[i] - min]减一然后放进newArray数组里面
            newArray[--counts[array[i] - min]] = array[i];
        }

        //将有序数组newArray赋值到array[]
        for (int i = 0; i < newArray.length; i++) {
            array[i] = newArray[i];
        }
    }
}